pair = {')':'(', ']':'[', '}':'{'}

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) % 2 == 1:  # 这一步真的机智
            return False

        l = [None]  # 通过一个初始化解决了边界情况
        for c in s:
            if c in pair and pair[c] == l[-1]:
                l.pop()
            else:
                l.append(c)
        return len(l) == 1


s = Solution()
print(s.isValid('[]'))
print(s.isValid('()[]{}'))
print(s.isValid('(]'))
print(s.isValid('([)]'))
print(s.isValid('{[]}'))
